1. Field of the Invention
The present invention relates to a computer-based memory system, and, more particularly, to methods to maintain triangle ordering of coherence message in multiprocessor systems.
2. Description of the Related Art
A symmetric multiprocessor (“SMP”) system generally employs a snoopy mechanism to ensure cache coherence among multiple caches. When a cache miss occurs in a requesting cache, the requesting cache broadcasts a cache request to other caches and the memory in the SMP system. When a supplying cache receives the cache request, the supplying cache performs a cache snoop operation and produces a snoop response indicating whether the requested data is found in the cache, and the state of the corresponding cache line if the requested data is found. If the requested data is found in an appropriate cache state, the supplying cache can supply the data to the requesting cache via a cache intervention. The memory is responsible for supplying the requested data to the requesting cache if the snoop responses show that the requested data cannot be supplied from any of the other caches.
Many snoopy cache coherence protocols have been proposed. The MESI protocol and its variations are widely used in SMP systems. The MESI protocol has four cache states, namely modified (M), exclusive (E), shared (S) and invalid (I). At any time, a cache line in a cache can be in one of the four cache states (or possibly some transient state). If a cache line is in the invalid state, the data is not valid in the cache. If a cache line is in the shared state, the data is valid in the cache and can also be valid in other caches. The shared state is entered when the data is retrieved from the memory or another cache, and the corresponding snoop responses indicate that the data is valid in at least one of the other caches. If a cache line is in the exclusive state, the data is valid in the cache, and cannot be valid in another cache. Furthermore, the data has not been modified with respect to the data maintained at the memory. The exclusive state is entered when the data is retrieved from the memory or another cache, and the corresponding snoop responses indicate that the data is not valid in another cache. If a cache line is in the modified state, the data is valid in the cache and cannot be valid in another cache. Furthermore, the data has been modified as a result of a store operation.
When a cache miss occurs, if the requested data is found in both the memory and another cache, supplying the data to the requesting cache via a cache intervention is often preferred because cache-to-cache transfer latency is usually smaller than memory access latency. The IBM® Power 4 system, for example, enhances the MESI protocol to allow more cache interventions. An enhanced coherence protocol allows data of a shared cache line to be supplied to another cache via a cache intervention. In addition, if data of a modified cache line is supplied to another cache, the modified data is not necessarily written back to the memory immediately. A cache with the most up-to-date data can be held responsible for memory update when the data is eventually replaced.
Referring now to FIG. 1, in a modern SMP system, caches can be connected with each other via a message-passing interconnect instead of a shared bus to improve system scalability and performance. In a bus-based SMP system, the bus behaves as a central arbitrator that serializes all bus transactions to ensure a total order of bus transactions. In a network-based SMP system, in contrast, when a requesting cache broadcasts a message, the message is not necessarily received at the same time by the caches that receive the message. As a result, different messages can potentially be received in different orders at different receiving caches.
Therefore, the following set of chronological events is possible: (1) Cache A broadcasts a first message to caches B and C; (2) cache B receives the first message from cache A and then sends a second message to cache C; and (3) cache C receives the second message from cache B before receiving the first message from cache. As apparent to those skilled in the art, a problem affecting the correctness of cache coherence may arise if the first message from cache A affects the second message generated at cache B, and the order in which the messages are received at cache C affects the coherence action taken at cache C. We refer to this scenario as a “violation of triangle ordering” because the messages involved logically form a triangle.
Referring now to FIG. 2, an exemplary diagram of a simple triangle ordering violation is shown. Chronological events are labeled using event numbers in parentheses, such that a lower numbered event occurs before a higher numbered event, unless otherwise noted. Thus, event (1) occurs before event (2), which occurs before event (3), etc. FIG. 2 illustrates the occurrence of a chronological set of events (1) through (5). The simple triangle ordering violation involves three caches and two broadcast messages. The caches are represented using circles A, B and C, respectively. The messages are represented by directional lines between caches. Although FIG. 2 involves only three caches and two messages, it should be appreciated that a triangle ordering violation may involve more than three caches and more than two messages, as contemplated by those skilled in the art. FIG. 2 illustrates the following sequence of chronological events.                (1) Cache A broadcasts a first message to caches B and C.        (2) Cache B receives the first message from cache A.        (3) Cache B sends a second message to cache C.        (4) Cache C receives the second message from cache B.        (5) Cache C receives the first message from cache B.        
FIGS. 3 and 4 illustrate two examples demonstrating that correctness of cache coherence can be compromised when a broadcast or multicast message can be received at different times at different caches. It should be appreciated, however, that one skilled in the art would contemplate other scenarios that would cause a triangle ordering violation.
Referring now to FIG. 3, an exemplary diagram is shown in which cache coherence can be violated when an invalidate request is not observed atomically. Assume, that data of an address is initially shared in caches A and C. Further assume that cache C can source the shared data to another cache via a cache intervention. FIG. 3 illustrates the following sequence of chronological events.
(1) Cache A broadcasts an invalidate request to caches B and C to claim the exclusive ownership of the cache line. This may happen, for example, when a processor associated with cache A performs a store operation to the address.
(2) Cache B receives the invalidate request from cache A, and sends an invalidate acknowledgment to cache A. The invalidate acknowledgment indicates that the data is not found in cache B.
(3) Cache B broadcasts a data request to cache A and cache C (the data request to cache A is not shown). This may happen, for example, when a processor associated with cache B performs a load operation to the address.
(4) Cache C receives the data request from cache B, and sends a data reply to cache B to supply a shared copy of the data. Note that cache C receives the data request from cache B before receiving the invalidate request from cache A.
(5) Cache C receives the invalidate request from cache A, invalidates the shared copy from cache C, and sends an invalidate acknowledgment to cache A.
(6) Cache B receives the data reply from cache C, and caches the data in a shared state.
(7) Cache A receives the invalidate acknowledgments from caches B and C; and claims the exclusive ownership of the cache line. As a result, data of the cache line can be modified in cache A, leaving a stale copy in cache B. This clearly violates cache coherence of the system.
Referring now to FIG. 4, an exemplary diagram is shown in which cache coherence can be violated when a data request is not observed atomically. It is assumed that cache C initially includes data of an address in an exclusive state. FIG. 4 illustrates the following sequence of chronological events.
(1) Cache A broadcasts a data request to caches B and C. This may occur, for example, when a processor associated with cache A performs a load operation.
(2) Cache B receives the data request from cache A, and sends an invalid acknowledgment to cache A. The invalid acknowledgment indicates that the requested data is not found in cache B.
(3) Cache B broadcasts a read-with-intent-to-modify (hereinafter “RWITM”) request to caches A and C. This may occur, for example, when a processor associated with cache B performs a store operation. The intent of the RWITM request is to obtain data of the address while claiming the exclusive ownership of the corresponding cache line.
(4) Cache C receives the RWITM request before receiving the data request from cache A, and sends a RWITM reply to cache B to supply the data and the exclusive ownership. The cache line is invalidated from cache C.
(5) Cache C receives the data request from cache A, and sends an invalid acknowledgment to cache A. The invalid acknowledgment indicates that the requested data is not found in cache C.
(6) Cache B receives the RWITM reply from cache C, and caches the data in an exclusive state.
(7) Cache A receives the invalid acknowledgments from caches B and C, and retrieves the requested data from the memory because the invalid acknowledgments falsely indicate that the requested data is not cached in caches B and C. As a result, cache A may obtain a stale copy from the memory, because cache B, with the exclusive ownership of the cache line, may have modified the data without updating the memory.
Several methods have been proposed to guarantee correctness of cache coherence in SMP systems in which caches are interconnected via a message-passing network. One method is to retry certain coherence operations when potential races conditions are detected, which can often result in serious performance penalty and intractable protocol complexity. Another method is to rely on certain ordering guarantees provided by an underlying network or network topology. For example, consider an SMP system in which caches communicate with each other via a unidirectional ring. When a cache intends to broadcast a message, it sends the message to its next cache, which receives the message while forwarding it to its next cache, and so on. It becomes apparent that this message passing mechanism can eliminate violation of triangle ordering, assuming first-in-first-out (“FIFO”) message passing between neighboring caches.
Another method is token coherence, which has been proposed to support cache coherence on networks without any message ordering guarantee. It associates a fixed number of tokens with each memory line at the cache line granularity. Tokens are held with caches and memory, and can be transferred using coherence messages. A processor can read a cache line only if the cache line holds at least one token. A processor can write a cache line only when the cache line holds all the tokens. A major drawback of token coherence is the extra cost of maintaining tokens, including storage at both cache and memory sides and coherence actions for token transfers.